/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/top-k-frequent-words
   @Language: C++
   @Datetime: 19-03-31 14:51
   */

class Solution {
	typedef pair<string,int> Word;
	struct comp{
		bool operator()(const Word &a, const Word &b)const{
			if (a.second!=b.second) return a.second > b.second;   // minheap
			else return less<string>()(a.first,b.first);    // dict order
		}
	};
public:
	/**
	 * @param words: an array of string
	 * @param k: An integer
	 * @return: an array of string
	 */
	vector<string> topKFrequentWords(vector<string> &words, int k) {
		// write your code here
		priority_queue<Word,vector<Word>,comp> minheap;
		unordered_map<string,int> dict;
		for(const auto &w:words)
			dict[w]++;
		for(const auto &w:dict){
			minheap.push(w);
			if (minheap.size()>k) minheap.pop();
		}
		vector<string> vs(minheap.size(),"0");
		for(int n=minheap.size(); minheap.size(); minheap.pop())
			vs[--n]=minheap.top().first;
		return vs;
	}
};
